package leetcode;

import list.ListNode;

public class PalindromeLinkedList {

	public boolean isPalindrome(ListNode head) {
		// 首先想一想，实现O(1)空间和O(n)时间的难点在哪，因为链表没有指向前面结点的指针
		// 所以我们无法同时遍历后半部分与前半部分
		// 但是我们可以将前半部分逆转，这样子就实现了遍历
		if (head == null || head.next == null) {
			return true;
		}
		int length = 0;
		ListNode node = head;
		while (node != null) {
			node = node.next;
			length++;
		}
		// 逆转前半部分
		ListNode pre = null;
		ListNode next = null;
		node = head;
		int middleLength = length / 2;
		int curIndex = 0;
		while (curIndex < middleLength) {
			next = node.next;
			node.next = pre;
			pre = node;
			node = next;
			curIndex++;
		}
		// 还原的时候需要连接的结点
		ListNode middleNode = node;
		// 此时开始遍历两部分
		ListNode left = pre;
		// 可能有奇偶之分
		ListNode right = (length & 1) == 1 ? middleNode.next : node;
		boolean res = true;
		while (left != null) {
			if (left.val != right.val) {
				res = false;
				break;
			} else {
				left = left.next;
				right = right.next;
			}
		}

		// 最后还要还原原有的链表
		ListNode pre1 = null;
		next = null;
		node = pre; // pre此时是新的头结点了
		while (node != null) {
			next = node.next;
			node.next = pre1;
			pre1 = node;
			node = next;
		}
		pre.next = middleNode;
		return res;
	}
}
